package DP;

import java.util.Arrays;

/**
 * @Classname 打家劫舍198
 * @Description TODO
 * @Date 2023/3/28 8:54
 * @Created by xjl
 */
public class 打家劫舍198 {
    /**
     * @description 利用递归来实现 从后向前推进
     * @param: nums
     * @date: 2023/3/28 8:55
     * @return: int
     * @author: xjl
     */
    private int[] nums, cache;

    public int rob(int[] nums) {
        this.nums = nums;
        int n = nums.length;
        cache = new int[n];
        Arrays.fill(cache, -1);
        return dfs(n - 1);
    }

    private int dfs(int i) {
        if (i < 0) {
            return 0;
        }
        if (cache[i] != -1) {
            return cache[i];
        }
        return cache[i] = Math.max(dfs(i - 1), dfs(i - 2) + nums[i]);
    }

    /**
     * @description 使用的迭代的思想 从前向后的进行计算
     * @param: nums
     * @date: 2023/3/28 9:02
     * @return: int
     * @author: xjl
     */
    public int rob2(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 2];
        for (int i = 0; i < n; ++i) {
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n + 1];
    }

    /**
     * @description 直接采用斐波拉契方式赋值 来直接保留结果
     * @param: nums
     * @date: 2023/3/28 9:03
     * @return: int
     * @author: xjl
     */
    public int rob3(int[] nums) {
        int f0 = 0, f1 = 0;
        for (int x : nums) {
            int newF = Math.max(f1, f0 + x);
            f0 = f1;
            f1 = newF;
        }
        return f1;
    }

    public int rob6(int[] nums) {
        if (nums.length <= 1) {
            return nums.length == 0 ? 0 : nums[0];
        }
        /*
            dp[i] 截止到这一家，我能够拿到的最大钱数是多少
        */
        int[] dp = new int[nums.length];
        int res = nums[1] > nums[0] ? nums[1] : nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {dp[0] = nums[0];continue;}
            if (i == 1) {dp[1] = Math.max(nums[0], nums[1]);continue;}
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
            res = Math.max(dp[i], res);
        }
        return res;
    }
}
